package com.cuz.daileetcode;

public class Day65 {


    /****
     * 两种硬币的组合方式
     * @param ordinaryArray 普通币
     * @param specialCoin 特殊币
     * @param target 目标
     * @return 种数
     */
    public static int coinGetTogether(int[] ordinaryArray, int[] specialCoin, int target) {
        if (ordinaryArray == null || specialCoin == null) {
            return 0;
        }
        // oDp[i][j] 表示 ordinaryArray【0.。。i】的前随便用凑出j元的 种数
        int oLen = ordinaryArray.length;
        int[][] oDp = new int[oLen][target + 1];
        //oDp[?][0]表示随便用钱凑出0元 那么方法只有一种 那就是一张不用
        for (int index = 0; index < oLen; index++) {
            oDp[index][0] = 1;
        }
        //oDp[0][?]表示ordinaryArray[0]面值的钱随便用 凑出？元的方法数
        //只有？ 是 ordinaryArray[0]整数种数为1
        for (int index = 0; index <= target; index++) {
            if ((index % ordinaryArray[index]) == 0) {
                oDp[0][index] = 1;
            }
        }
        for (int row = 1; row < oLen; row++) {
            //当前新增可以用的钱
            int curCoin = ordinaryArray[row];
            for (int col = 1; col <= target; col++) {
                //可以用当前这个钱 使用 1到col/curCoin张
                //也可以不用 那么就等于 oDp[row-1][col]
                //二者加起来
                oDp[row][col] += oDp[row - 1][col];
//                //尝试 用1到 col/curCoin 那么就是问用row-1之前的前
//                for (int index=1;index<(col/curCoin);index++){
//                    oDp[row][col]+=oDp[row-1][col-index*curCoin];
//                }
                //可以优化为
                if (col - curCoin >= 0) {
                    oDp[row][col] += oDp[row][col - curCoin];
                }
            }
        }

        int sLen = specialCoin.length;
        int[][] sDp = new int[sLen][target + 1];
        for (int index = 0; index < sLen; index++) {
            // 0...index 处的钱随便用 凑出 0元的种数 就是1
            sDp[index][0] = 1;
        }
        //只有 specialCoin[0]处的钱 只可以凑出 specialCoin[0]的面值 因为只能使用一张
        if (specialCoin[0] <= target) {
            sDp[0][specialCoin[0]] = 1;
        }
        for (int row = 1; row < oLen; row++) {
            //当前新增可以用的钱
            int curCoin = specialCoin[row];
            for (int col = 1; col <= target; col++) {
                //可以选择使用当前的钱 用一张
                if (curCoin <= target) {
                    sDp[row][col] += sDp[row - 1][target - curCoin];
                }
                //可以选择不使用当前的钱
                sDp[row][col] += sDp[row - 1][col];
            }
        }
        int sum = 0;
        //普通硬币凑index元 特殊硬币凑 target-index 元
        for (int index = 0; index < target; index++) {
            sum += oDp[oLen - 1][index] * sDp[sLen - 1][target - index];
        }
        return sum;

    }


    public static double midNumOfTwoArray(int[] arr1, int[] arr2) {
        int len1 = arr1.length;
        int len2 = arr2.length;
        if (len1 > len2) {
            return midNumOfTwoArray(arr2, arr1);
        }
        int min = 0;
        int max = len1;
        int maxLeft = 0;
        int maxRight = 0;
        while (min <= max) {
            int i = (min + max) / 2;
            int j = (len1 + len2 + 1) / 2 - i;
            if (j != 0 && i != max) {
                if (arr2[j - 1] > arr1[i]) {
                    min = i + 1;
                } else if (arr1[i - 1] > arr2[j]) {
                    max = i - 1;
                }
            } else {

                if (i == 0) {
                    maxLeft = arr2[j - 1];
                } else if (j == 0) {
                    maxLeft = arr1[i - 1];
                }
                if ((len1 + len2) % 2 == 1) {
                    return maxLeft;
                }
                if (i == len1) {
                    maxRight = arr2[j];
                } else if (j == len2) {
                    maxRight = arr1[i];
                } else {
                    maxRight = Math.min(arr2[j], arr1[i]);
                }
            }
        }
        return (maxRight + maxLeft) / (2.0);
    }
}
